#include "BinaryTree.h"
#include <stdio.h>
#include <windows.h>


BinaryTree::BinaryTree(){

	// nodeNULL marks the free slots in the tree
	nodeNULL.value = -1;
	nodeNULL.left = -1;
	nodeNULL.right = -1; 
	
}

BinaryTree::~BinaryTree(){

}

void BinaryTree::setArbMemory(Node* vArb){

	// the memory address where the tree is stored
	arb = vArb;
	// initialize
	for (int i =0; i<BUFSIZE; i++){
		arb[i].value = nodeNULL.value;
		arb[i].right = nodeNULL.right;
		arb[i].left = nodeNULL.left;
	}

}

void BinaryTree::cloneArb(Node* vArb){

	arb = new Node[BUFSIZE];	
	memcpy(arb,vArb,BUFSIZE*sizeof(Node));
}


void BinaryTree::addNode(int x)
{
	short int i = findFree();	// finds a free slot
	if (i == -1)
	{
		printf("Buffer overflow!\n");// memory full
	}
	else
	{
		// new node = leaf
		Node newNode;
		newNode.value = x;
		newNode.left = -2;	// left = NULL
		newNode.right = -2;// right = NULL
		
		arb[i] = newNode;	// add the new node in the slot
		if (i != 0)			
			makeLinks(0,i);	// links the node in the tree
	}
}

// find a free slot
short int BinaryTree::findFree(){
	
	for (short int i = 0;i<BUFSIZE; i++)
		if (equal(arb[i],nodeNULL))
			return i;
	
	return -1;
}

// compares two nodes
int BinaryTree::equal(Node n1,Node n2){
		
		if (n1.value == n2.value && n1.left == n2.left && n1.right == n2.right)
			return 1;
		return 0;
}

void BinaryTree::makeLinks(short int root,short int i)
{
	if (arb[i].value < arb[root].value )
	{
		if (arb[root].left == -2)	// left = NULL
			arb[root].left = i;
		else
			makeLinks(arb[root].left,i);
	
	}
	else
	{
		if (arb[root].right == -2)	// right = NULL
			arb[root].right = i;	
		else
			makeLinks(arb[root].right,i);
	}

}

//  breadth first
void BinaryTree::printTree(short int root){
	
	int ps=0;
	int i = 0;
	int c[BUFSIZE*3];	
	int level[BUFSIZE*3];

	memset(level,0,BUFSIZE*3);
	if (!equal(arb[root],nodeNULL)){
		c[0] = root;  
		while (ps <= i)
		{
			if (ps>0 && level[ps] != level[ps - 1])
				printf("\n");
			if (c[ps] == -2)	// nod null
				printf("* ");
			else{
				printf("%d ",arb[c[ps]].value);
				c[++i] = arb[c[ps]].left;
				level[i] = level[ps] + 1;
				c[++i] = arb[c[ps]].right;
				level[i] = level[ps] + 1;
			}
			ps++;
		}
	}
	else
		printf("*");// arborele vid
	printf("\n");
}

// find the minimum for the subtree
short int BinaryTree::FindMin(short int root)
{
	short int temp = root;
	while (arb[temp].left != -2){
		temp = arb[temp].left;
	}
	return temp;
}

//  all the slots are empty
void BinaryTree::Clear(){

	for (int i=0;i<BUFSIZE;i++)
		arb[i] = nodeNULL;

}


// delete a node witch has a the value x
short int BinaryTree::Delete(int x, short int  root){

	short int temp;
	if (root != -2)// root =-2 =>the node was not found 
	{
            if( x < arb[root].value ) 	
              arb[root].left = Delete( x, arb[root].left );
            else
            if( x > arb[root].value ) 
               arb[root].right = Delete( x, arb[root].right );
            else  // s-a gasit nodul
            if( arb[root].left != -2 && arb[root].right !=-2 ) // there are two children
            {
                temp = FindMin( arb[root].right );	
                arb[root].value = arb[temp].value;	
                arb[root].right = Delete(arb[root].value, arb[root].right );
				}
            else  
            {
         
				if( arb[root].left == -2 && arb[root].right != -2 ){	// only one child  right side(
                    temp = arb[root].right ;
					arb[root] = arb[arb[root].right];					//  replace the value
					arb[temp] = nodeNULL;								// deletes the node
				}
				else if( arb[root].right == -2 && arb[root].left != -2 ){	// only one child left side
                    temp = arb[root].left ;
					arb[root] = arb[arb[root].left];						
					arb[temp] = nodeNULL;
				}
				else
				{
					arb[root] = nodeNULL;								// it is a leaf
					return -2;
				}
					
            }
	}

    return root;
	 
}
